#include <vector>
using namespace std;



//version 1 自己写的！
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size(), left = -1, right = n, i = 0;
        while(i < right){
            if(nums[i] == 0) std::swap(nums[++left], nums[i]);
            else if(nums[i] == 2) std::swap(nums[--right], nums[i]);
            else ++i;

            if(left == i) ++i;
        }
    }
};



//version 2 看了题解写的 其实和Leetcode_283类似 就是给数组分区！
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size(), left = -1, right = n , i = 0;
        while(i < right){
            if(nums[i] == 0) std::swap(nums[++left], nums[i++]);
            else if(nums[i] == 1) ++i;
            else std::swap(nums[i], nums[--right]);
        }
    }
};